package algorithm.middle;

import pojo.TreeNode;

public class InsertIntoMaxTree998 {
    /**
     * case1：如果val大于root.val，则root就是val节点的左子树节点。
     * case2：如果val大于非root.val，则非root就是val节点的左子树节点，并且非root节点的原父节点的右子树更新为val节点。
     * case3：如果val小于最底层的叶子节点，则val节点就作为该叶子节点的右子树节点。
     *
     * 作者：muse-77
     * 链接：https://leetcode.cn/problems/maximum-binary-tree-ii/solution/by-muse-77-zkfg/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (val > root.val) {
            TreeNode treeNode = new TreeNode(val);
            treeNode.left = root;
            return treeNode;
        }
        buildTree(root, val);
        return root;
    }

    public void buildTree(TreeNode node,int  val) {
        if (node.right==null){
            node.right = new TreeNode(val);
        } else if (node.right.val < val) {
            node.right = new TreeNode(val, node.right, null);
        }else {
            buildTree(node.right, val);
        }
    }


}
